1. Field of the Invention
The present invention relates generally to systems and methods for generating halftone images, and more particularly, to a method of designing sets of color matrices that tile together for use in creating color halftone images.
2. Description of the Prior Art
Digital halftoning refers to any process that creates the illusion of continuous-tone images by judicious arrangement of the binary picture elements, such as ink drops in the case of inkjet printers. Thus, halftoning is printing the simulation of a continuous-tone image, such as a shaded drawing or photograph with groups or cells of color or black dots. The dots are placed in such a way that they appear to the human eye to be a single color.
There are many halftoning techniques, each with its own method for laying down dots. Suppose a source color image is represented by the red, green and blue components. The simplest way of halftoning a color image using a dither matrix is to halftone each color plane independently using the same dither matrix. Each color defines a color concentration level. The term xe2x80x9ccolor concentration levelxe2x80x9d for a color image is analogous to the term xe2x80x9cgray levelxe2x80x9d for a black and white image. FIG. 1 shows a representation of a printing system for generating a color print image. The image planes 110a, 110b, 110c are representative of the red, green and blue color components of an image. A single dither matrix 120 is used to halftone each image independently to create halftone images 130a, 130b, 130c. To create the halftone images 130a, 130b, 130c, pixel values in the image planes 110a, 110b, 110c are compared to the corresponding entries in the dither matrix 120 to determine which of the pixel values should be turned on or off. Halftoning is accomplished by a simple pointwise comparison of the source image 110 against a predetermined threshold array or mask. For every point or pixel in the source image, depending on which point value is larger (i.e., the image or the mask), either a 1 or 0, respectively, is placed at the corresponding location in the binary output image.
Let the red, green and blue components of the source image 110 at pixel (m,n) be r(m,n), g(m,n) and b(m,n), respectively. If the dither matrix threshold value at the same position is t(m,n), then one of the most commonly used halftone rules is:
if r(m,n) less than t(m,n), print a cyan dot at (m,n);
if g(m,n) less than t(m,n), print a magenta dot at (m,n);
if b(m,n) less than t(m,n), print a yellow dot at (m,n).
Unfortunately, the basic halftoning technique described above creates an unacceptable level of artifacts in the resulting halftone image, leading to poor image quality. In response to this problem, U.S. Pat. No. 5,812,744 to Allebach et al. (hereinafter referred to as xe2x80x9cthe ""744 patentxe2x80x9d) describes a method of jointly designing a single set of color dither matrices. Referring to FIG. 2, which is taken from the ""744 patent, the method described in the ""744 patent generates a separate dither matrix 210a, 210b, 210c for each separate color image plane 220a, 220b, 220c, respectively. According to the ""744 patent, using a set of dither matrices (i.e., a separate dither matrix for each color plane) reduces the halftone texture and increases the sharpness of the halftone image without increasing the complexity of the computations required.
While the methods described in the ""744 patent clearly provided improvements to the existing technology, the set of dither matrices needed for the ""744 scheme consumes more memory than a single dither matrix for all color planes as utilized by the prior art. Accordingly, it is desirable to develop a mechanism that reduces the memory requirements while maintaining or improving the print quality provided by the dither matrices provided by the ""744 patent.
Moreover, halftoning in accordance with teachings of the ""744 patent occasionally introduces undesirable periodic artifacts that stem from having a single set of dither matrices for use in the halftoning process. As the desktop printers increase in resolution (e.g. with 120+dpi), the conventional 128xc3x97128 screens can produce a distinctive periodicity in the printed images.
In addition, it would be desirable to be able to encode information into a halftone image to determine the source of the print. As can be appreciated, the ability to identify the source of any print would have useful application in authentication and fraud detection (e.g., counterfeit detection). Unfortunately, when there is a single set of dither matrices, as is provided by the ""744, it is not possible to encode information into the resulting halftone image. Instead, multiple sets of dither matrices that can be utilized to halftone an image are required in order to encode information into the halftone image.
An example of using two sets of dither matrices (instead of one) to encode watermark information into dither hafltone images is described in xe2x80x9cWatermarking of Dither Halftoned Images,xe2x80x9d written by Z. Baharav and D. Shaked, and published in the Proceedings of SPIE, Vol. 3657 as part of the ISandT/SPIE Conference on Security and Watermarking of Multimedia Contents, San Jose, Calif., January 1999. However, this example is limited to black and white images.
As can be appreciated, such a security system is dependent on a mechanism to design or generate multiple sets of dither matrices that can be utilized to encode information and yet at the same time tile together seamlessly for good print quality. One approach to designing multiple sets of dither matrices that can tile together seamlessly is described in xe2x80x9cAperiodic Micro Screen Design using DBS and Training,xe2x80x9d written by D. Kacker and J. Allebach, and published in the Proceedings of SPIE, Vol. 3300 as part of the ISandT/SPIE Conference on Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III, San Jose, Calif., January 1998. Unfortunately, this screen design method is only applicable to monochrome images. Accordingly, it is desirable for there to be a mechanism for designing color dither matrices that tile together seamlessly so that a watermark system, as described above, can be implemented for color images.
Unfortunately, there is no current approach to design multiple sets of color dither matrices. Furthermore, as noted previously, any approach must consider the memory requirements of these multiple sets of dither matrices. It is preferable that the storage requirements of these sets of dither matrices be the same or less than the storage needed by the single set of dither matrices.
Accordingly, there remains a need for a method of generating multiple sets of color dither matrices that occupy less storage space, increases halftone image quality, and that enable the encoding of information in the halftone image.
A method for jointly designing at least two sets of dither matrices is described. First, a mosaic color tile is generated for a first concentration level according to a design tile map. The mosaic color tile includes at least a first color tile and a second color tile where each color tile has a color tile concentration level (CTCL) and a color tile number (CTN). Second, a color fluctuation metric is computed for the mosaic color tile. Next, the pixels in the first color tile are modified by an operation (e.g., a swap operation) while maintaining the first concentration level. Then, a color fluctuation metric is re-calculated on the mosaic color tile with all first color tiles being replaced with the modified first color tile (i.e., everywhere the first color tile appears in the mosaic color tile as specified by the design tile map). The steps of modifying the color tiles and re-calculating the color fluctuation metric for the modified mosaic tile is performed until the metric is below a predetermined metric level or until further changes yield only a small decrease in the metric (i.e., the decrease in the metric is less than a predetermined decrease). The other concentration levels are processed in like manner. When all concentration levels have been processed, color dither matrices are generated.